Market adoption of wireless LAN (WLAN) technology has exploded, as users from a wide range of backgrounds and vertical industries have brought this technology into their homes, offices, and increasingly into the public air space. This inflection point has highlighted not only the limitations of earlier-generation systems, but the changing role WLAN technology now plays in people's work and lifestyles, across the globe. Indeed, WLANs are rapidly changing from convenience networks to business-critical networks. Increasingly users are depending on WLANs to improve the timeliness and productivity of their communications and applications, and in doing so, require greater visibility, security, management, and performance from their network.
As enterprises and other entities increasingly rely on wireless networks, the appropriate deployment and configuration of wireless access points in a wireless network environment becomes critical to performance and security. To ascertain the coverage and other performance attributes of a wireless network deployment, RF prediction can be used to construct site-specific models of RF signal propagation in a given wireless network environment. RF prediction uses mathematical techniques, such as ray tracing, to model the effects of physical obstructions, such as walls, doors, windows, and the like, on RF signal propagation in a desired environment. For example, S. Fortune, “Algorithms for Prediction of Indoor Radio Propagation,” Technical Memorandum, Bell Laboratories (1998), disclose various algorithms that can be used to predict radio signal propagation. Valenzuela et al., “Indoor Propagation Prediction Accuracy and Speed Versus Number of Reflections in Image-Based 3-D Ray-Tracing,” Technical Document, Bell Laboratories (1998), describe algorithms for modeling RF signal propagation in indoor environments. In addition, Rajkumar et al., “Predicting RF Coverage in Large Environments using Ray-Beam Tracing and Partitioning Tree Represented Geometry,” Technical Document, AT&T Bell Laboratories (1995), also disclose methods for predicting RF signal propagation in site specific environments.
Still further, the rapid proliferation of lightweight, portable computing devices and high-speed WLANs enables users to remain connected to various network resources, while roaming throughout a building or other physical location. The mobility afforded by WLANs has generated a lot of interest in applications and services that are a function of a mobile user's physical location. Examples of such applications include: printing a document on the nearest printer, locating a mobile user or rogue access point, displaying a map of the immediate surroundings, and guiding a user inside a building. The required or desired granularity of location information varies from one application to another. Indeed, the accuracy required by an application that selects the nearest network printer, or locates a rogue access point, often requires the ability to determine in what room a wireless node is located. Accordingly, much effort has been dedicated to improving the accuracy of wireless node location mechanisms.
The analysis of radio signal attenuation to estimate the location of a wireless device or node is known. Signal attenuation refers to the weakening of a signal over its path of travel due to various factors like terrain, obstructions and environmental conditions. Generally speaking, the magnitude or power of a radio signal weakens as it travels from its source. The attenuation undergone by an electromagnetic wave in transit between a transmitter and a receiver is referred to as path loss. Path loss may be due to many effects such as free-space loss, refraction, reflection, and absorption. In many business enterprise environments, most location-tracking systems are based on RF triangulation or RF fingerprinting techniques. RF fingerprinting compares the strength of signals transmitted by infrastructure access points (or mobile stations) with a database that contains an RF physical model of the coverage area. This database is typically populated by either an extensive site survey or by the use of RF prediction to develop a model of RF signal propagation in a given environment. For example, Bahl et al., “A Software System for Locating Mobile Users: Design, Evaluation, and Lessons,” describes an RF location system (the RADAR system) in a WLAN environment, that allows a mobile station to track its own location relative to access points in a WLAN environment. In addition, the patent applications identified above describe a location tracking system that estimates the location of a mobile station based on the signal strengths of the mobile stations, as detected by access points in a WLAN environment.
RF prediction algorithms typically require that a given environment be modeled as a series of discrete physical objects, including location information and other physical parameters, such as wall type and the like. To that end, vector models are used to model the physical environments. A vector model is, in essence, an abstraction of various physical objects where positional data is represented in the form of coordinates. In vector data, the basic units of spatial information are points and lines. For example, a line can be expressed as a pair of coordinate locations corresponding to the end points of the line. Each vector object is self-contained, with properties such as color, shape, thickness, size, and position. Accordingly, RF prediction algorithms require a vector model of a desired physical environment that, often times, does not exist. Indeed, most drawings of an office building (for example) that are available to network administrators are scanned, raster images of planning drawings. A raster drawing or image is an image represented by a sequence of pixels (picture elements) or points, which when taken together, describe the display of an image on an output device.
Some current technologies require a user to take a base CAD or basic raster drawing (i.e. JPG, GIF, BMP, etc.) and, within a vector modeling application, trace over it to create a vector model of the same drawing. Often times, however, this process can be time consuming as a large number of physical objects must be modeled, such as walls, partitions, etc. In addition, the amount of time required to produce vector models for a large number of buildings and other locations can be prohibitive. The need arises, therefore, for technologies that convert generic building, facility, or location diagrams and translate them into a form that the computer can actually use for calculations of distance, topology type, and wall type. To that end, raster-to-vector conversion software has been developed. For example, the AlgoLab Raster to Vector Conversion Toolkit, offered by AlgoLab, Inc. of London, Ontario, Canada, converts architectural, mechanical and various technical drawings from raster to vector formats. This allows a user to scan a paper drawing to create a raster image file. The raster-to-vector conversion software operates on the raster image file to automatically recognize line artwork and represent the image in a vector format that then can be imported to a CAD or drawing program.
While the raster-to-vector conversion software according to the prior art works for its intended objectives, these technologies are not specifically adapted to modeling of RF propagation in physical locations. For example, prior art raster-to-vector conversion technologies often create vector models that, sometimes due to the attributes of the raster image, include a number of small vector objects that together correspond to a single wall or other object in the actual physical environment. For example, an image including a diagonal line often appears jagged after it has been scanned, causing many prior art raster-to-vector conversion tools to create a plurality of vector objects. Optimally, however, RF prediction algorithms operate more efficiently and accurately when the wall is represented as a single vector object. As another example, walls are often represented in schematic drawings with two or more parallel lines. For purposes of RF prediction, these multiple parallel lines must be converted into a single vector object. In addition, the scanned and vectorized images may also include small pieces of information noise due to the graininess (or other artifacts) in the raster image, as well as other objects, that are not relevant to modeling RF propagation. These circumstances often require a user to make substantial modifications to the vector model, such as creating a single object to represent a wall, and erasing small objects that represent noise or are otherwise irrelevant (or have a de minimis impact) to RF propagation.
In light of the foregoing, a need exists in the art for methods, apparatuses and systems that facilitate the modeling of RF environments for use in RF prediction and other technologies that model RF propagation. Embodiments of the present invention substantially fulfill this need.